home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / rbcell.jav < prev    next >
Text File  |  1995-12-14  |  17KB  |  638 lines
  1. /*
  2.   File: RBCell.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.  
  12. */
  13.   
  14. package collections;
  15.  
  16. import java.util.Enumeration;
  17. import java.util.NoSuchElementException;
  18.  
  19. /**
  20.  * RBCell implements basic capabilities of Red-Black trees,
  21.  * an efficient kind of balanced binary tree. The particular
  22.  * algorithms used are adaptations of those in Corman,
  23.  * Lieserson, and Rivest's <EM>Introduction to Algorithms</EM>.
  24.  * This class was inspired by (and code cross-checked with) a 
  25.  * similar class by Chuck McManis. The implementations of
  26.  * rebalancings during insertion and deletion are
  27.  * a little trickier than those versions since they
  28.  * don't swap cell contents or use a special dummy nilnodes. 
  29.  * <P>
  30.  * It is a pure implementation class. For harnesses, see:
  31.  * @see RBTree
  32.  * @author Doug Lea
  33.  * @version 0.93
  34.  *
  35.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  36.  *
  37. **/
  38.  
  39.  
  40.  
  41.  
  42. public class RBCell extends Cell implements ImplementationCheckable  {
  43.   static final boolean RED   = false;
  44.   static final boolean BLACK = true;
  45.  
  46. /**
  47.  * The node color (RED, BLACK)
  48. **/
  49.  
  50.   protected boolean color_;
  51.  
  52. /**
  53.  * Pointer to left child
  54. **/
  55.  
  56.   protected RBCell  left_;
  57.  
  58. /**
  59.  * Pointer to right child
  60. **/
  61.  
  62.   protected RBCell  right_;
  63.  
  64. /**
  65.  * Pointer to parent (null if root)
  66. **/
  67.  
  68.   private RBCell  parent_;
  69.  
  70. /**
  71.  * Make a new cell with given element, null links, and BLACK color.
  72.  * Normally only called to establish a new root.
  73. **/
  74.  
  75.   public RBCell(Object element) { 
  76.     super(element);
  77.     left_ = null; right_ = null; parent_ = null; color_ = BLACK;
  78.   }
  79.  
  80. /**
  81.  * Return a new RBCell with same element and color as self,
  82.  * but with null links. (Since it is never OK to have
  83.  * multiple identical links in a RB tree.)
  84. **/
  85.   protected Object clone() throws CloneNotSupportedException { 
  86.     RBCell t = new RBCell(element());
  87.     t.color_ = color_;
  88.     return t;
  89.   }
  90.  
  91.   
  92. /** 
  93.  * Return left child (or null)
  94. **/
  95.  
  96.   public final RBCell left()   { return left_; }
  97.  
  98. /** 
  99.  * Return right child (or null)
  100. **/
  101.  
  102.   public final RBCell right()  { return right_; }
  103.  
  104. /** 
  105.  * Return parent (or null)
  106. **/
  107.   public final RBCell parent() { return parent_; }
  108.  
  109.  
  110. /**
  111.  * @see collections.ImplementationCheckable.checkImplementation.
  112. **/
  113.   public void checkImplementation() 
  114.   throws ImplementationError {
  115.  
  116.    // It's too hard to check the property that every simple
  117.    // path from node to leaf has same number of black nodes.
  118.    // So restrict to the following
  119.  
  120.     assert(parent_ == null || 
  121.       this == parent_.left_ || 
  122.       this == parent_.right_);
  123.  
  124.     assert(left_ == null ||
  125.       this == left_.parent_);
  126.  
  127.     assert(right_ == null ||
  128.       this == right_.parent_);
  129.  
  130.     assert(color_ == BLACK || 
  131.       (colorOf(left_) == BLACK) && (colorOf(right_) == BLACK));
  132.  
  133.     if (left_ != null) left_.checkImplementation();
  134.     if (right_ != null) right_.checkImplementation();
  135.   }
  136.       
  137. /**
  138.  * Implements collections.ImplementationCheckable.assert.
  139.  * @see collections.ImplementationCheckable#assert
  140. **/
  141.   public void assert(boolean pred) 
  142.   throws ImplementationError {
  143.     ImplementationError.assert(this, pred);
  144.   }
  145.  
  146.  
  147. /**
  148.  * Return the minimum element of the current (sub)tree
  149. **/
  150.   
  151.   public final RBCell leftmost() {
  152.     RBCell p = this;
  153.     for ( ;  p.left_ != null; p = p.left_) {}
  154.     return p;
  155.   }
  156.  
  157. /**
  158.  * Return the maximum element of the current (sub)tree
  159. **/
  160.   public final RBCell rightmost() {
  161.     RBCell p = this;
  162.     for ( ; p.right_ != null; p = p.right_) {}
  163.     return p;
  164.   }
  165.  
  166. /**
  167.  * Return the root (parentless node) of the tree
  168. **/
  169.   public final RBCell root() {
  170.     RBCell p = this;
  171.     for ( ; p.parent_ != null; p = p.parent_) {}
  172.     return p;
  173.   }
  174.  
  175. /**
  176.  * Return true if node is a root (i.e., has a null parent)
  177. **/
  178.  
  179.   public final boolean isRoot() { return parent_ == null; }
  180.  
  181.  
  182. /**
  183.  * Return the inorder successor, or null if no such
  184. **/
  185.  
  186.   public final RBCell successor() {
  187.     if (right_ != null)
  188.       return right_.leftmost();
  189.     else {
  190.       RBCell p = parent_;
  191.       RBCell ch = this;
  192.       while (p != null && ch == p.right_) { ch = p; p = p.parent_; }
  193.       return p;
  194.     }
  195.   }
  196.  
  197. /**
  198.  * Return the inorder predecessor, or null if no such
  199. **/
  200.  
  201.   public final RBCell predecessor() {
  202.     if (left_ != null)
  203.       return left_.rightmost();
  204.     else {
  205.       RBCell p = parent_;
  206.       RBCell ch = this;
  207.       while (p != null && ch == p.left_) { ch = p; p = p.parent_; }
  208.       return p;
  209.     }
  210.   }
  211.  
  212. /**
  213.  * Return the number of nodes in the subtree
  214. **/
  215.   public final int size() {
  216.     int c = 1;
  217.     if (left_ != null) c += left_.size();
  218.     if (right_ != null) c += right_.size();
  219.     return c;
  220.   }
  221.  
  222.  
  223. /**
  224.  * Return node of current subtree containing element as element(), 
  225.  * if it exists, else null. 
  226.  * Uses Comparator cmp to find and to check equality.
  227. **/
  228.  
  229.   public RBCell find(Object element, Comparator cmp) {
  230.     RBCell t = this;
  231.     for (;;) {
  232.       int diff = cmp.compare(element, t.element());
  233.       if (diff == 0) return t;
  234.       else if (diff < 0) t = t.left_;
  235.       else t = t.right_;
  236.       if (t == null) return null;
  237.     }
  238.   }
  239.  
  240.  
  241. /**
  242.  * Return number of nodes of current subtree containing element.
  243.  * Uses Comparator cmp to find and to check equality.
  244. **/
  245.   public int count(Object element, Comparator cmp) {
  246.     int c = 0;
  247.     RBCell t = this;
  248.     while (t != null) {
  249.       int diff = cmp.compare(element, t.element());
  250.       if (diff == 0) {
  251.         ++c;
  252.         if (t.left_ == null)
  253.           t = t.right_;
  254.         else if (t.right_ == null)
  255.           t = t.left_;
  256.         else {
  257.           c += t.right_.count(element, cmp);
  258.           t = t.left_;
  259.         }
  260.       }
  261.       else if (diff < 0) t = t.left_;
  262.       else  t = t.right_;
  263.     }
  264.     return c;
  265.   }
  266.  
  267.  
  268.  
  269.  
  270. /**
  271.  * Return a new subtree containing each element of current subtree
  272. **/
  273.  
  274.   public RBCell copyTree() {
  275.     RBCell t = null;
  276.     try {
  277.       t = (RBCell)(clone());
  278.     } catch (CloneNotSupportedException ex) {}
  279.  
  280.     if (left_ != null) {
  281.       t.left_ = left_.copyTree();
  282.       t.left_.parent_ = t;
  283.     }
  284.     if (right_ != null) {
  285.       t.right_ = right_.copyTree();
  286.       t.right_.parent_ = t;
  287.     }
  288.     return t;
  289.   }
  290.  
  291.  
  292. /**
  293.  * There's no generic element insertion. Instead find the
  294.  * place you want to add a node and then invoke insertLeft
  295.  * or insertRight.
  296.  * <P>
  297.  * Insert cell as the left child of current node, and then
  298.  * rebalance the tree it is in.
  299.  * @param cell the cell to add
  300.  * @param root, the root of the current tree
  301.  * @return the new root of the current tree. (Rebalancing
  302.  * can change the root!)
  303. **/
  304.  
  305.  
  306.   public RBCell insertLeft(RBCell cell, RBCell root) {
  307.     left_ = cell;
  308.     cell.parent_ = this;
  309.     return cell.fixAfterInsertion(root);
  310.   }
  311.  
  312. /**
  313.  * Insert cell as the right child of current node, and then
  314.  * rebalance the tree it is in.
  315.  * @param cell the cell to add
  316.  * @param root, the root of the current tree
  317.  * @return the new root of the current tree. (Rebalancing
  318.  * can change the root!)
  319. **/
  320.  
  321.   public RBCell insertRight(RBCell cell, RBCell root) {
  322.     right_ = cell;
  323.     cell.parent_ = this;
  324.     return cell.fixAfterInsertion(root);
  325.   }
  326.  
  327.     
  328. /**
  329.  * Delete the current node, and then rebalance the tree it is in
  330.  * @param root the root of the current tree
  331.  * @return the new root of the current tree. (Rebalancing
  332.  * can change the root!)
  333. **/
  334.  
  335.  
  336.   public RBCell delete(RBCell root) {
  337.  
  338.     // handle case where we are only node
  339.     if (left_ == null && right_ == null && parent_ == null) return null;
  340.  
  341.     // if strictly internal, swap places with a successor
  342.     if (left_ != null && right_ != null) {
  343.       RBCell s = successor();
  344.       // To work nicely with arbitrary subclasses of RBCell, we don't want to
  345.       // just copy successor's fields. since we don't know what
  346.       // they are.  Instead we swap positions in the tree.
  347.       root = swapPosition(this, s, root);
  348.     }
  349.  
  350.     // Start fixup at replacement node (normally a child).
  351.     // But if no children, fake it by using self
  352.  
  353.     if (left_ == null && right_ == null) {
  354.       
  355.       if (color_ == BLACK) 
  356.         root = this.fixAfterDeletion(root);
  357.  
  358.       // Unlink  (Couldn't before since fixAfterDeletion needs parent ptr)
  359.  
  360.       if (parent_ != null) {
  361.         if (this == parent_.left_) 
  362.           parent_.left_ = null;
  363.         else if (this == parent_.right_) 
  364.           parent_.right_ = null;
  365.         parent_ = null;
  366.       }
  367.  
  368.     }
  369.     else {
  370.       RBCell replacement = left_;
  371.       if  (replacement == null) replacement = right_;
  372.        
  373.       // link replacement to parent 
  374.       replacement.parent_ = parent_;
  375.  
  376.       if (parent_ == null)             root = replacement; 
  377.       else if (this == parent_.left_)  parent_.left_  = replacement;
  378.       else                             parent_.right_ = replacement;
  379.  
  380.       left_ = null;
  381.       right_ = null;
  382.       parent_ = null;
  383.  
  384.       // fix replacement
  385.       if (color_ == BLACK) 
  386.         root = replacement.fixAfterDeletion(root);
  387.       
  388.     }
  389.  
  390.     return root;
  391.   }
  392.  
  393. /**
  394.  * Swap the linkages of two nodes in a tree.
  395.  * Return new root, in case it changed.
  396. **/
  397.  
  398.   static RBCell swapPosition(RBCell x, RBCell y, RBCell root) {
  399.  
  400.    /* Too messy. TODO: find sequence of assigments that are always OK */
  401.  
  402.     RBCell px = x.parent_; 
  403.     boolean xpl = px != null && x == px.left_;
  404.     RBCell lx = x.left_;
  405.     RBCell rx = x.right_;
  406.  
  407.     RBCell py = y.parent_;
  408.     boolean ypl = py != null && y == py.left_;
  409.     RBCell ly = y.left_;
  410.     RBCell ry = y.right_;
  411.  
  412.     if (x == py) {
  413.       y.parent_ = px;
  414.       if (px != null) if (xpl) px.left_ = y; else px.right_ = y;
  415.       x.parent_ = y;
  416.       if (ypl) { 
  417.         y.left_ = x; 
  418.         y.right_ = rx; if (rx != null) rx.parent_ = y;
  419.       }
  420.       else {
  421.         y.right_ = x;
  422.         y.left_ = lx;   if (lx != null) lx.parent_ = y;
  423.       }
  424.       x.left_ = ly;   if (ly != null) ly.parent_ = x;
  425.       x.right_ = ry;  if (ry != null) ry.parent_ = x;
  426.     }
  427.     else if (y == px) {
  428.       x.parent_ = py;
  429.       if (py != null) if (ypl) py.left_ = x; else py.right_ = x;
  430.       y.parent_ = x;
  431.       if (xpl) { 
  432.         x.left_ = y; 
  433.         x.right_ = ry; if (ry != null) ry.parent_ = x;
  434.       }
  435.       else {
  436.         x.right_ = y;
  437.         x.left_ = ly;   if (ly != null) ly.parent_ = x;
  438.       }
  439.       y.left_ = lx;   if (lx != null) lx.parent_ = y;
  440.       y.right_ = rx;  if (rx != null) rx.parent_ = y;
  441.     }
  442.     else {
  443.       x.parent_ = py; if (py != null) if (ypl) py.left_ = x; else py.right_ = x;
  444.       x.left_ = ly;   if (ly != null) ly.parent_ = x;
  445.       x.right_ = ry;  if (ry != null) ry.parent_ = x;
  446.       
  447.       y.parent_ = px; if (px != null) if (xpl) px.left_ = y; else px.right_ = y;
  448.       y.left_ = lx;   if (lx != null) lx.parent_ = y;
  449.       y.right_ = rx;  if (rx != null) rx.parent_ = y;
  450.     }
  451.  
  452.     boolean c = x.color_; x.color_ = y.color_; y.color_ = c;
  453.  
  454.     if (root == x) root = y;
  455.     else if (root == y) root = x;
  456.     return root;
  457.   }
  458.  
  459.  
  460.  
  461. /**
  462.  * Return color of node p, or BLACK if p is null
  463.  * (In the CLR version, they use
  464.  * a special dummy `nil' node for such purposes, but that doesn't
  465.  * work well here, since it could lead to creating one such special
  466.  * node per real node.)
  467.  *
  468. **/
  469.  
  470.   static boolean colorOf(RBCell p) { return (p == null)? BLACK : p.color_; }
  471.  
  472. /**
  473.  * return parent of node p, or null if p is null
  474. **/
  475.   static RBCell  parentOf(RBCell p) { return (p == null)? null: p.parent_; }
  476.  
  477. /**
  478.  * Set the color of node p, or do nothing if p is null
  479. **/
  480.  
  481.   static void    setColor(RBCell p, boolean c) { if (p != null)  p.color_ = c; }
  482.  
  483. /**
  484.  * return left child of node p, or null if p is null
  485. **/
  486.  
  487.   static RBCell  leftOf(RBCell p) { return (p == null)? null: p.left_; }
  488.  
  489. /**
  490.  * return right child of node p, or null if p is null
  491. **/
  492.  
  493.   static RBCell  rightOf(RBCell p) { return (p == null)? null: p.right_; }
  494.  
  495.       
  496.   /** From CLR **/
  497.   protected final RBCell rotateLeft(RBCell root) {
  498.     RBCell r = right_;
  499.     right_ = r.left_;
  500.     if (r.left_ != null) r.left_.parent_ = this;
  501.     r.parent_ = parent_;
  502.     if (parent_ == null) root = r;
  503.     else if (parent_.left_ == this) parent_.left_ = r;
  504.     else parent_.right_ = r;
  505.     r.left_ = this;
  506.     parent_ = r;
  507.     return root;
  508.   }
  509.  
  510.   /** From CLR **/
  511.   protected final RBCell rotateRight(RBCell root) {
  512.     RBCell l = left_;
  513.     left_ = l.right_;
  514.     if (l.right_ != null) l.right_.parent_ = this;
  515.     l.parent_ = parent_;
  516.     if (parent_ == null) root = l;
  517.     else if (parent_.right_ == this) parent_.right_ = l;
  518.     else parent_.left_ = l;
  519.     l.right_ = this;
  520.     parent_ = l;
  521.     return root;
  522.   }
  523.  
  524.  
  525.   /** From CLR **/
  526.   protected final RBCell fixAfterInsertion(RBCell root) {
  527.     color_ = RED;
  528.     RBCell x = this;
  529.     
  530.     while (x != null && x != root && x.parent_.color_ == RED) {
  531.       if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  532.         RBCell y = rightOf(parentOf(parentOf(x)));
  533.         if (colorOf(y) == RED) {
  534.           setColor(parentOf(x), BLACK);
  535.           setColor(y, BLACK);
  536.           setColor(parentOf(parentOf(x)), RED);
  537.           x = parentOf(parentOf(x));
  538.         }
  539.         else {
  540.           if (x == rightOf(parentOf(x))) {
  541.             x = parentOf(x);
  542.             root = x.rotateLeft(root);
  543.           }
  544.           setColor(parentOf(x), BLACK);
  545.           setColor(parentOf(parentOf(x)), RED);
  546.           if (parentOf(parentOf(x)) != null) 
  547.             root = parentOf(parentOf(x)).rotateRight(root);
  548.         }
  549.       }
  550.       else {
  551.         RBCell y = leftOf(parentOf(parentOf(x)));
  552.         if (colorOf(y) == RED) {
  553.           setColor(parentOf(x), BLACK);
  554.           setColor(y, BLACK);
  555.           setColor(parentOf(parentOf(x)), RED);
  556.           x = parentOf(parentOf(x));
  557.         }
  558.         else {
  559.           if (x == leftOf(parentOf(x))) {
  560.             x = parentOf(x);
  561.             root = x.rotateRight(root);
  562.           }
  563.           setColor(parentOf(x),  BLACK);
  564.           setColor(parentOf(parentOf(x)), RED);
  565.           if (parentOf(parentOf(x)) != null) 
  566.             root = parentOf(parentOf(x)).rotateLeft(root);
  567.         }
  568.       }
  569.     }
  570.     root.color_ = BLACK;
  571.     return root;
  572.   }
  573.   
  574.  
  575.  
  576.   /** From CLR **/
  577.   protected final RBCell fixAfterDeletion(RBCell root) {
  578.     RBCell x = this;
  579.     while (x != root && colorOf(x) == BLACK) {
  580.      if (x == leftOf(parentOf(x))) {
  581.        RBCell sib = rightOf(parentOf(x));
  582.        if (colorOf(sib) == RED) {
  583.          setColor(sib, BLACK);
  584.          setColor(parentOf(x), RED);
  585.          root = parentOf(x).rotateLeft(root);
  586.          sib = rightOf(parentOf(x));
  587.        }
  588.        if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
  589.          setColor(sib,  RED);
  590.          x = parentOf(x);
  591.        }
  592.        else {
  593.          if (colorOf(rightOf(sib)) == BLACK) {
  594.            setColor(leftOf(sib), BLACK);
  595.            setColor(sib, RED);
  596.            root = sib.rotateRight(root);
  597.            sib = rightOf(parentOf(x));
  598.          }
  599.          setColor(sib, colorOf(parentOf(x)));
  600.          setColor(parentOf(x), BLACK);
  601.          setColor(rightOf(sib), BLACK);
  602.          root = parentOf(x).rotateLeft(root);
  603.          x = root;
  604.        }
  605.      }
  606.      else {
  607.        RBCell sib = leftOf(parentOf(x));
  608.        if (colorOf(sib) == RED) {
  609.          setColor(sib, BLACK);
  610.          setColor(parentOf(x), RED);
  611.          root = parentOf(x).rotateRight(root);
  612.          sib = leftOf(parentOf(x));
  613.        }
  614.        if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
  615.          setColor(sib,  RED);
  616.          x = parentOf(x);
  617.        }
  618.        else {
  619.          if (colorOf(leftOf(sib)) == BLACK) {
  620.            setColor(rightOf(sib), BLACK);
  621.            setColor(sib, RED);
  622.            root = sib.rotateLeft(root);
  623.            sib = leftOf(parentOf(x));
  624.          }
  625.          setColor(sib, colorOf(parentOf(x)));
  626.          setColor(parentOf(x), BLACK);
  627.          setColor(leftOf(sib), BLACK);
  628.          root = parentOf(x).rotateRight(root);
  629.          x = root;
  630.        }
  631.      }
  632.    }
  633.     setColor(x, BLACK);
  634.     return root;
  635.   }
  636.            
  637. }
  638.